package leetcode.tree.binary.traversal;

import leetcode.tree.binary.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 236. 二叉树的最近公共祖先
 *
 */
public class LowestCommonAncestor {

    /**
     * 全局变量 保存最近公共祖先节点
     */
    private TreeNode ans = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }


    /**
     * 方法一 递归
     *
     * 方法作用: root为根节点的子树中是否包含 p节点或 q节点
     *
     * 本质
     *      一个后序遍历的模型, 每个父节点都会接收子节点的状态(是否含有p、q)
     *      并把这个状态往上传递, 直到该结点满足祖先节点的条件
     *
     * @param root  当前
     * @param p     指定的 p节点
     * @param q     指定的 q节点
     * @return
     */
    public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        //在当前节点
        boolean inCurrentNode = root.val == p.val || root.val == q.val;
        //在左节点
        boolean inLeft = dfs(root.left, p, q);
        //在右节点
        boolean inRight = dfs(root.right, p, q);

        // 1 如果左右子树分别包含了p节点或 q节点, 那么当前节点就是公共祖先节点
        // 2 当前节点正好是p节点或 q节点并且它的左子树或右子树有一个包含了另一个节点, 那么当前节点就是公共祖先节点
        if ((inLeft && inRight) || (inCurrentNode && (inLeft || inRight))) {
            ans = root;
        }

        // root为根节点的子树中是否包含 p节点或 q节点 = 左右子树包含p节点或 q节点 || 当前节点的值就是p节点或 q节点的值
        return inLeft || inRight || inCurrentNode;
    }


    /**
     * 方法二 存储父节点
     *
     */
    Map<Integer, TreeNode> parent = new HashMap<>();
    Set<Integer> visited = new HashSet<>();

    /**
     * 深度优先遍历, 使用HashMap存储每个节点的值和对应的父节点对象
     *
     * @param root  树对象
     */
    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        // 获取每个节点的值和对应的父节点对象的HashMap
        dfs(root);

        // 从 p 节点开始不断往它的祖先移动, 使用Set存储已经访问过的祖先节点
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        //  q节点开始不断往它的祖先移动, 如果有祖先已经被访问过, 即意味着这是 p 和 q 的最近公共祖先节点
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

}
